11401. Игра

 

В свободное время Фидан и Фуад играют дома. На этот раз они придумали новую игру:

·        Фуад берет чистый лист бумаги.

·     Фидан называет одно число. Если это число уже записано на бумаге, Фуад стирает его. В противном случае, если числа на бумаге нет, он записывает его. Этот процесс повторяется  раз.

·        В конце игры Фидан должна определить, сколько чисел осталось записанными на бумаге.

 

Числа, называемые Фидан, заданы последовательностью a1, a2, ..., an – в том порядке, в котором она их произносила. Помогите Фидан определить, сколько различных чисел останется на бумаге в конце игры.

 

Вход. Первая строка содержит одно целое число n (1 ≤ n ≤ 105). Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109).

 

Выход. Выведите количество чисел, оставшихся на бумаге к концу игры.

 

Пример входа 1

Пример выхода 1

4

5 7 4 5

2

 

 

Пример входа 2

Пример выхода 2

6

1 2 3 2 3 1

0

 

 

РЕШЕНИЕ

структуры данных – set

 

Анализ алгоритма

Будем моделировать игру с помощью структуры данных – множества (set). Множество будет хранить все числа, записанные на бумаге.

Каждый раз, когда Фидан называет число, Фуад проверяет, содержится ли оно в множестве:

·        если содержится – он удаляет это число из множества (стирает его с бумаги);

·        если не содержится – он добавляет число в множество (записывает на бумагу).

Количество чисел, оставшихся на бумаге к концу игры, совпадает с количеством элементов в множестве.

 

Пример

Промоделируем работу множества для первого и второго примеров.

 

В конце игры:

·        Первое множество содержит 2 элемента;

·        Второе множество пустое (содержит 0 элементов);

 

Реализация алгоритма

Читаем количество чисел n.

 

scanf("%d", &n);

 

Последовательно обрабатываем n чисел, названных Фидан.

 

for (i = 0; i < n; i++)

{

  scanf("%d", &x);

 

Каждый раз, когда Фидан называет число x:

·        Если числа x нет во множестве, добавляем его.

·        Если число x уже присутствует во множестве, удаляем его.

 

  if (s.find(x) == s.end())

    s.insert(x);

  else

    s.erase(x);

}

 

Выводим ответ – размер множества s.

 

printf("%d\n", s.size());

 

Python реализация

Читаем входные данные.

 

n = int(input())

lst = map(int,input().split())

 

Объявляем множество.

 

s = set()

 

Последовательно обрабатываем числа, названные Фидан.

 

for x in lst:

 

Каждый раз, когда Фидан называет число x:

·        Если число x уже присутствует во множестве, удаляем его.

·        Если числа x нет во множестве, добавляем его.

 

  if x in s:

    s.remove(x)

  else:

    s.add(x)

 

Выводим ответ – размер множества s.

 

print(len(s))